package leetcode;

import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class LeetCodeSolutionTwo {
    public static void main(String[] args) {
        long startTime = new Date().getTime();

        String s = "(1+(4+5+2)-3)+(6+8)";
        System.out.println("re:"+ climbStairs(7));


        System.out.println("耗时：" + (new Date().getTime() - startTime));
    }
    // https://leetcode.cn/problems/climbing-stairs/submissions/527301871/?envType=study-plan-v2&envId=top-interview-150
    // 爬楼梯 动态规划
    public static int climbStairs2(int n) {
        if (n<=2) return n;
        int a=1,b=2,sum;
        for (int i = 2; i < n; i++) {
            sum = a + b;
            a = b;
            b = sum;
        }
        return b;
    }

    // https://leetcode.cn/problems/climbing-stairs/submissions/527301871/?envType=study-plan-v2&envId=top-interview-150
    // 爬楼梯 递归超时
    public static int climbStairs(int n) {
        if (n<=2) return n;
        return  climbStairs(n-1)+climbStairs(n-2);
    }
    // https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/?envType=study-plan-v2&envId=top-interview-150
    // 逆波兰表达式求值
    public static int evalRPN(String[] tokens) {
        int result = 0;
        if (tokens.length == 1) {
            return new Integer(tokens[0]);
        }
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            switch (token) {
                case "+":
                    result = stack.pop() + stack.pop();
                    stack.push(result);
                    break;
                case "-":
                    int temp3 = stack.pop();
                    int temp4 = stack.pop();
                    result = temp4 - temp3;
                    stack.push(result);
                    break;
                case "*":
                    result = stack.pop() * stack.pop();
                    stack.push(result);
                    break;
                case "/":
                    int temp = stack.pop();
                    int temp2 = stack.pop();
                    result = temp2 / temp;
                    stack.push(result);
                    break;
                default:
                    stack.push(new Integer(token));
                    break;
            }
        }
        return result;
    }

    // https://leetcode.cn/problems/simplify-path/description/?envType=study-plan-v2&envId=top-interview-150
    // 简化路径
    public static String simplifyPath(String path) {
        Stack<String> strings = new Stack<>();
        for (String s : path.replaceAll("//", "/").split("/")) {
            if (!s.isEmpty()) {
                if (s.equals(".")) {
                } else if (s.equals("..") && !strings.empty()) {
                    strings.pop();
                } else {
                    if (!s.equals("..")) {
                        strings.push(s);
                    }
                }
            }
        }
        StringBuilder result = new StringBuilder();
        while (!strings.empty()) {
            result.insert(0, "/" + strings.pop());
        }
        return result.toString().isEmpty() ? "/" : result.toString();
    }

    // https://leetcode.cn/problems/valid-parentheses/?envType=study-plan-v2&envId=top-interview-150
    // 有效的括号
    public boolean isValid(String s) {
        Map<String, String> map = new HashMap<>();
        map.put("(", ")");
        map.put("{", "}");
        map.put("[", "]");
        Stack<String> strings = new Stack<>();
        for (String s1 : s.split("")) {
            if (strings.empty()) {
                if (map.containsValue(s1)) return false;
                strings.push(s1);
            } else {
                if (map.containsValue(s1)) {
                    if (!map.get(strings.peek()).equals(s1)) return false;
                    else strings.pop();
                } else {
                    strings.push(s1);
                }
            }
        }

        return strings.empty();
    }

    // https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/?envType=study-plan-v2&envId=top-interview-150
    // 用最少数量的箭引爆气球
    public int findMinArrowShots2(int[][] points) {
        if (points == null || points.length == 0) return 0;
        Arrays.sort(points, (p1, p2) -> p1[0] < p2[0] ? -1 : 1);
        int start = points[0][0], end = points[0][1], counts = 1;
        for (int i = 1; i < points.length; i++) {
            // 当前区间与初始区间存在交集
            if (points[i][0] <= end) {
                start = Math.max(points[i][0], start);
                end = Math.min(points[i][1], end);
            } else {
                // 不存在交集，更新起始点，箭数加1
                counts++;
                start = points[i][0];
                end = points[i][1];
            }
        }
        return counts;
    }

    // https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/?envType=study-plan-v2&envId=top-interview-150
    // 用最少数量的箭引爆气球
    public static int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (p1, p2) -> p1[0] < p2[0] ? -1 : 1);
        Map<Integer, Integer> imap = new HashMap<>();
        for (int[] interval : points) {
            boolean flag = true;
            int s = interval[0], e = interval[1];
            // 注:需要用 iterator 删除map
            Iterator<Map.Entry<Integer, Integer>> iterator = imap.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<Integer, Integer> entry = iterator.next();
                // 判断是否存在重合区间 不重合直接略过
                if ((entry.getKey() > interval[1] || entry.getValue() < interval[0])) {
                } else {
                    flag = false;
                    // 若重合 则获取最小重合区间
                    s = Math.max(entry.getKey(), s);
                    e = Math.min(entry.getValue(), e);
                    // 规避已经缩小到最小的区间 被删除的情况
                    if (!entry.getKey().equals(entry.getValue())) {
                        iterator.remove();
                    }

                }
            }
            if (flag) {
                imap.put(interval[0], interval[1]);
            } else {
                imap.put(s, e);
            }
        }
        for (Map.Entry<Integer, Integer> entry : imap.entrySet()) {
            System.out.println(entry.getKey() + "-" + entry.getValue());
        }
        return imap.size();
    }
}
